COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	% This program by D. E. Knuth is not copyrighted and can be used freely.
C00004 00003	@* Introduction.
C00011 00004	@* The character set.
C00016 00005	@* Inputting the data.
C00019 00006	@* Pixel compensation.
C00026 00007	@* The main program.
C00027 00008	@* Index.
C00038 ENDMK
C⊗;
% This program by D. E. Knuth is not copyrighted and can be used freely.

% Here is TeX material that gets inserted after \input webmac
\def\title{HALFTONES}
\font\mc=cmr9

\def\con{\par\vfill\eject % finish the section names
  \rightskip 0pt \hyphenpenalty 50 \tolerance 200
  \setpage
  \output{\normaloutput\page\lheader\rheader}
  \titletrue % prepare to output the table of contents
  \pageno=\contentspagenumber \def\rhead{TABLE OF CONTENTS}
  \message{Table of contents:}
  \topofcontents
  \line{{\bf Sample}\hfil Section}
  \def\Z##1##2##3{\line{\ignorespaces##1
    \leaders\hbox to .5em{.\hfil}\hfil\hbox to2em{\hss##2}}}
  \readcontents\relax % read the contents info
  \botofcontents \end} % print the contents page(s) and terminate
@* Introduction.
This program prepares 17-level halftone images for use in \TeX\ files. The
input is assumed to be a sequence of pictures expressed in the form
$$\halign{\qquad#\hfil\cr
$m\quad n$\cr
$\langle\,$first line of pixel data, $n$ characters long$\,\rangle$\cr
\ \ \ \dots\cr
$\langle\,m$th line of pixel data, $n$ characters long$\,\rangle$\cr}$$
terminated by a line that says simply `\.0'.
The pixel data consists of the characters |"0"| to~|"9"| and
|"A"| to~|"V"|, representing 32 levels of darkness from black to white.
[This convention was adopted from the appendix to {\sl Digital Image
Processing\/} by Gonzalez and Wintz (Addison-Wesley, 1977).]
@↑Gonzalez, Rafael C.@>
@↑Wintz, Paul@>

The output is the same set of pictures, expressed in a simple format used
for 17-level halftones, with ASCII characters |"0"| to |"@"| representing
darkness levels from white to black. The levels are adjusted to compensate
for the idiosyncrasies of Canon {\mc LBP-CX} laser-printing engines.

@ Here's an outline of the entire Pascal program:

@p program halfdots(@!input,@!output);
label @<Labels in the outer block@>@/
const @<Constants in the outer block@>@/
type @<Types in the outer block@>@/
var@?@<Global variables@>@/
@#
procedure initialize; {this procedure gets things started properly}
	var@?@<Local variables for initialization@>@/
	begin @<Set initial values@>@;
	end;@#
begin initialize; @<The main program@>;
end.

@ Each picture in the input data must contain fewer than |max_m| rows and
|max_n| columns.

@<Constants in the outer block@>=
@!max_m=200; {$m$ should be less than this}
@!max_n=200; {$n$ should be less than this}

@ The main program has one statement label, namely |cleanup_and_terminate|.

@d cleanup_and_terminate=9998
@d finish==goto cleanup_and_terminate
 {do this when all the pictures have been output}

@<Labels in...@>=cleanup_and_terminate;

@ It's convenient to declare a macro for incrementation.

@d incr(#) == #←#+1
@* The character set.
We need translation tables between ASCII and the actual character
set, in order to make this program portable. The standard conventions of
{\sl \TeX: The Program\/} are copied here, essentially verbatim.

@d text_char == char {the data type of characters in text files}
@d first_text_char=0 {ordinal number of the smallest element of |text_char|}
@d last_text_char=127 {ordinal number of the largest element of |text_char|}

@<Types...@>=
@!ASCII_code=0..127; {seven-bit numbers}

@ @<Glob...@>=
@!xord: array [text_char] of ASCII_code;
	{specifies conversion of input characters}
@!xchr: array [ASCII_code] of text_char;
	{specifies conversion of output characters}

@ @<Set init...@>=
xchr[@'40]←' ';
xchr[@'41]←'!';
xchr[@'42]←'"';
xchr[@'43]←'#';
xchr[@'44]←'$';
xchr[@'45]←'%';
xchr[@'46]←'&';
xchr[@'47]←'''';@/
xchr[@'50]←'(';
xchr[@'51]←')';
xchr[@'52]←'*';
xchr[@'53]←'+';
xchr[@'54]←',';
xchr[@'55]←'-';
xchr[@'56]←'.';
xchr[@'57]←'/';@/
xchr[@'60]←'0';
xchr[@'61]←'1';
xchr[@'62]←'2';
xchr[@'63]←'3';
xchr[@'64]←'4';
xchr[@'65]←'5';
xchr[@'66]←'6';
xchr[@'67]←'7';@/
xchr[@'70]←'8';
xchr[@'71]←'9';
xchr[@'72]←':';
xchr[@'73]←';';
xchr[@'74]←'<';
xchr[@'75]←'=';
xchr[@'76]←'>';
xchr[@'77]←'?';@/
xchr[@'100]←'@@';
xchr[@'101]←'A';
xchr[@'102]←'B';
xchr[@'103]←'C';
xchr[@'104]←'D';
xchr[@'105]←'E';
xchr[@'106]←'F';
xchr[@'107]←'G';@/
xchr[@'110]←'H';
xchr[@'111]←'I';
xchr[@'112]←'J';
xchr[@'113]←'K';
xchr[@'114]←'L';
xchr[@'115]←'M';
xchr[@'116]←'N';
xchr[@'117]←'O';@/
xchr[@'120]←'P';
xchr[@'121]←'Q';
xchr[@'122]←'R';
xchr[@'123]←'S';
xchr[@'124]←'T';
xchr[@'125]←'U';
xchr[@'126]←'V';
xchr[@'127]←'W';@/
xchr[@'130]←'X';
xchr[@'131]←'Y';
xchr[@'132]←'Z';
xchr[@'133]←'[';
xchr[@'134]←'\';
xchr[@'135]←']';
xchr[@'136]←'↑';
xchr[@'137]←'_';@/
xchr[@'140]←'`';
xchr[@'141]←'a';
xchr[@'142]←'b';
xchr[@'143]←'c';
xchr[@'144]←'d';
xchr[@'145]←'e';
xchr[@'146]←'f';
xchr[@'147]←'g';@/
xchr[@'150]←'h';
xchr[@'151]←'i';
xchr[@'152]←'j';
xchr[@'153]←'k';
xchr[@'154]←'l';
xchr[@'155]←'m';
xchr[@'156]←'n';
xchr[@'157]←'o';@/
xchr[@'160]←'p';
xchr[@'161]←'q';
xchr[@'162]←'r';
xchr[@'163]←'s';
xchr[@'164]←'t';
xchr[@'165]←'u';
xchr[@'166]←'v';
xchr[@'167]←'w';@/
xchr[@'170]←'x';
xchr[@'171]←'y';
xchr[@'172]←'z';
xchr[@'173]←'{';
xchr[@'174]←'|';
xchr[@'175]←'}';
xchr[@'176]←'~';@/
xchr[0]←' '; xchr[@'177]←' ';
	{ASCII codes 0 and |@'177| do not appear in text}

@ @<Local variables for init...@>=
i:0..last_text_char;

@ @<Set init...@>=
for i←1 to @'37 do xchr[i]←' ';
for i←first_text_char to last_text_char do xord[chr(i)]←@'177;
for i←1 to @'176 do xord[xchr[i]]←i;
@* Inputting the data.
We keep the pixel values in a big global array called |v|.
The variables |m| and~|n| keep track of the current number of rows
and columns in use.

The |dd| table contains density values assumed for the input,
indexed by single-character codes.

@<Glob...@>=
@!v:array [1..max_m,0..max_n] of real; {pixel darknesses, from 0.0 to 1.0}
@!m:integer; {rows |1..m+1| of |v| should contain relevant data}
@!n:integer; {columns |0..n+1| of |v| should contain relevant data}
@!dd:array[text_char] of real;

@ All input codes give zero density, except |"0"| to~|"9"| and
|"A"| to |"V"|.

@<Set init...@>=
for i←first_text_char to last_text_char do dd[chr(i)]←0.0;
for i←"0" to "9" do dd[chr(i)]←1.0-(i-"0")/31.0;
for i←"A" to "V" do dd[chr(i)]←1.0-(i-"A"+10)/31.0;

@ The process of inputting pixel values is quite simple. We terminate the
program if anomalous values of |m| and~|n| occur.  Extra zeros are added
at the left, right, and bottom in order to provide ``padding'' that will
be convenient in the pixel transformation process.

@<Input a picture, or terminate the program@>=
read(m);@+if (m≤0)∨(m≥max_m) then finish;
read_ln(n);@+if (n≤0)∨(n≥max_n) then finish;
for i:=1 to m do
	begin for j:=1 to n do
		begin read(c); v[i,j]:=dd[c];
		end;
	v[i,0]:=0.0; v[i,n+1]:=0.0;@/
	read_ln;
	end;
for j:=0 to n+1 do v[m+1,j]:=0.0

@ The code just written makes use of three temporary registers that must
be declared:

@<Glob...@>=
@!i,@!j:integer; {current row and column}
@!c:char; {character read from input}
@!cc:ASCII_code; {ASCII equivalent of |c|}
@* Pixel compensation.
The 17-level output of this program is assumed to be printed by a font
that contains $4\times4$ characters, where each character has 0 to~16
black bits. Physical properties of output devices cause distortions,
so that a character with |k| black bits does not have an apparent
density of |k/16|. We therefore maintain a table of apparent density
values.

@d max_l=16 {maximum output level}

@<Glob...@>=
@!d:array[0..max_l] of real; {apparent densities, from 0.0 to 1.0}

@ This table is based on some densitometer measurements that are not
especially reliable. The amount of toner seems to vary between the top of
a page and the bottom; also blocks of character |"n"| seem to appear
darker than blocks of the character |"o"|, because of some property of
xerography, although the |"o"| has one more bit turned on. Such
anomalies have been smoothed out here, since the resulting values should
prove good enough in practice.

@<Set init...@>=
d[0]:=0.0;
d[1]:=0.095;@/
d[2]:=0.155;
d[3]:=0.215;
d[4]:=0.27;
d[5]:=0.3;
d[6]:=0.32;@/
d[7]:=0.34;
d[8]:=0.36;
d[9]:=0.38;
d[10]:=0.42;
d[11]:=0.47;@/
d[12]:=0.53;
d[13]:=0.61;
d[14]:=0.71;
d[15]:=0.84;
d[16]:=1.0;

@ We convert the pixel values by using a variant of the Floyd-Steinberg
algorithm for adaptive grayscale [Society for Information Display,
{\sl SID 75 Digest}, 36--37].
@↑Floyd, Robert W@>
@↑Steinberg, Louis@>
The idea is to find the best available density, then to diffuse the error
into adjacent pixels that haven't yet been processed.

The following code assumes that |x| is the desired density value
in row~|i| and column~|j|. It outputs one 65-level density,
then updates |x| and~|j| in preparation for the next column in row~|i|.
Pixel values in row~|i+1| are modified to compensate for errors in
the current row.

@<Output one value and move to the next column@>=
@<Find |l| so that |d[l]| is as close as possible to |x|@>;
if odd(i+j) then write(xchr["A"+l])@+else write(xchr["a"+l]);
err←x-d[l];@/
v[i+1,j-1]:=v[i+1,j-1]+alpha*err;@/
v[i+1,j]:=v[i+1,j]+beta*err;@/
incr(j); {move right}
v[i+1,j]:=v[i+1,j]+gamma*err;@/
x:=v[i,j]+delta*err

@ Here is the overall control of the process.
Every line of the picture is a sequence of ASCII characters from |"0"| to |"p"|,
terminated by |"."|.

@<Output the picture@>=
for i:=1 to m do
	begin j:=1; x:=v[i,1];
	repeat @<Output one value...@>;
	until j>n;
	write_ln('.');
	end

@ It turns out to be desirable to
throw away about 10\% of the error. This dampens ``history'' effects
that the algorithm might otherwise introduce.

@<Set init...@>=
alpha:=3/18; {error diffusion to SW neighbor}
beta:=5/18; {error diffusion to S neighbor}
gamma:=1/18; {error diffusion to SE neighbor}
delta:=7/18; {error diffusion to E neighbor}

@ Here we use a straightforward binary search.

@<Find |l| so that |d[l]| is as close as possible to |x|@>=
if x≤0.0 then l←0
else if x≥1.0 then l←max_l
else	begin low_l←0; high_l←max_l; {we have |d[low_l]≤x<d[high_l]|}
	while high_l-low_l>1 do
		begin mid_l:=(low_l+high_l) div 2;
		if x≥d[mid_l] then low_l:=mid_l
		else high_l:=mid_l;
		end;
	if x-d[low_l]≤d[high_l]-x then l←low_l@+else l←high_l;
	end

@ We had better declare the variables we've been using.

@<Glob...@>=
@!x:real; {current pixel density}
@!err:real; {difference between |x| and the best we can achieve}
@!alpha,@!beta,@!gamma,@!delta:real; {constants of error diffusion}
@!l,@!low_l,@!mid_l,@!high_l:0..max_l; {trial density levels}
@* The main program.
Now we're ready to put all the pieces together.

@<The main program@>=
write_ln('\input hf17'); write_ln;
while true do
	begin @<Input a picture...@>;
	write_ln('\beginhalftone');
	@<Output the pic...@>;
	write_ln('\endhalftone'); write_ln;
	end;
cleanup_and_terminate:
@* Index.
Here are the quantities declared and/or used in the program.
(The uses of single-letter variables aren't indexed.)